In [1]:
from heapq import heappop, heappush, heappushpop
In [2]:
def running_median(xs):
low, high = [], []
for x in xs:
if not high:
heappush(high, x)
else:
if len(high) > len(low):
if x > high[0]:
heappush(low, -heappushpop(high, x))
else:
heappush(low, -x)
else:
if x < -low[0]:
heappush(high, -heappushpop(low, -x))
else:
heappush(high, x)
if len(high) > len(low):
print(high[0])
else:
print((-low[0] + high[0]) / 2)
In [3]:
running_median([12, 4, 5, 3, 8, 7])
In [4]:
running_median(range(10))
In [5]:
running_median(reversed(range(5)))
In [6]:
running_median([12, 6, 1, 30, 8, 72])